#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_VALUE 500

typedef struct triplet
{
    int data; // 存储数据
    int x;    // 坐标x
    int y;    // 坐标y
} triplet;

typedef struct TSMatrix
{
    struct triplet element[MAX_VALUE];
    int m, n, num; // 分别代表行,列,非零元个数
} TSMatrix;

void show_TSMatrix(TSMatrix *tsMatrix, int rows, int cols)
{
    printf("----------------------输出三元组-----------------------\n");
    for (int i = 0; i < tsMatrix->num; i++)
    {
        printf("(%d,%d) %d\n", tsMatrix->element[i].x, tsMatrix->element[i].y, tsMatrix->element[i].data);
    }
    printf("----------------------输出三元组结束-----------------------\n");
}

void show_Matrix(int matrix[][5], int rows, int cols)
{
    printf("----------------------输出矩阵-----------------------\n");

    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    printf("----------------------输出矩阵结束-----------------------\n");
}

void Fast_Transpose(TSMatrix *M, TSMatrix *T) // 快速转置,把M转为T
{
    // 对换T与S行列,赋值非零元个数
    T->m = M->n;
    T->n = M->m;
    T->num = M->num;

    // 建立两个数组num[]和p[]用来存放非零元个数与这一列的第一个非零元素起始位置(大小等于M的列数)
    int num[M->n];
    int p[M->n];
    // 初始化数组
    for (int i = 0; i < M->n; i++)
    {
        num[i] = 0;
        p[i] = 0;
    }

    // 使用类似于计算众数的方法计算M每一列非零元个数
    for (int i = 0; i < M->num; i++)
    {
        num[M->element[i].y]++;
    }

    //计算每一列第一个值应该在三元表数组的哪个位置
    p[0] = 0;
    for (int i = 1; i < M->n; i++)
    {
        p[i] = p[i - 1] + num[i - 1]; // 前一列的起始位置加上前一列长度确定这一列第一个数的起始位置
    }

    for (int i = 0; i < M->num; i++) // 转置[对所有非零元操作]
    {
        // 获取这非零元应该在的行与列
        int col = M->element[i].y;         // 确定当前三元组所在的列数
        int place = p[col];                // 得到他转置后所在三元组的位置
        T->element[place] = M->element[i]; // 赋值
        // 更换x与y
        T->element[place].x = M->element[i].y; // 这里容易忘记也容易错
        T->element[place].y = M->element[i].x;
        ++p[col]; // 当前所在列起始位置加一,保证下一个此列元素的位置可以找对
    }
    return;
}

int main() // 三元组存储转制非方阵的矩阵
{
    // 建立一个矩阵
    int m = 4, n = 5;
    int matrix[4][5] =
        {
            {1, 2, 0, 4, 0},
            {0, 0, 1, 0, 0},
            {0, 0, 5, 0, 0},
            {4, 3, 0, 0, 3},
        };

    show_Matrix(matrix, m, n); // m=3,n=4,一个4*5的矩阵

    // 初始化一个三元表指针
    TSMatrix *M = (TSMatrix *)malloc(sizeof(TSMatrix));

    // 扫描矩阵,把矩阵非零元存储到三元表内
    int q = 0;
    for (int i = 0; i < m; i++) // 对行遍历
    {
        for (int j = 0; j < n; j++) // 对列遍历
        {
            if (matrix[i][j] != 0)
            {
                M->element[q].x = i;
                M->element[q].y = j;
                M->element[q].data = matrix[i][j];
                q++; // 计数器加一
            }
        }
    }
    M->m = m;   // m+1行
    M->n = n;   // n+1列
    M->num = q; // 存放非零元数量

    // 输出三元表
    show_TSMatrix(M, m, n);

    // 进行转制
    printf("----------------------进行转制-----------------------\n");

    TSMatrix *T = (TSMatrix *)malloc(sizeof(TSMatrix));
    Fast_Transpose(M, T); // 快速转制,[算法5.2]

    show_TSMatrix(T, m, n);

    // 输出三元组解压后的矩阵
    int new_Matrix[5][4] = {0}; // 转制后矩阵行列互换
    for (int i = 0; i < T->num; i++)
    {
        new_Matrix[T->element[i].x][T->element[i].y] = T->element[i].data;
    }

    // 输出转制后的新矩阵
    printf("----------------------输出转制后的新矩阵-----------------------\n");
    for (int i = 0; i < T->m; i++)
    {
        for (int j = 0; j < T->n; j++)
        {
            printf("%d ", new_Matrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}